Computer graphics workstations can provide highly detailed graphics simulations for a variety of applications. Engineers and designers working in the computer aided design (CAD) and computer aided manufacturing (CAM) areas typically utilize graphics simulations for a variety of computational tasks. The computer graphics workstation industry has thus been driven to provide more powerful computer graphics workstations which can perform graphics simulations quickly and with increased detail.
Modern workstations having graphics capabilities generally utilize "window" systems to organize graphics manipulations. As the industry has been driven to provide faster and more detailed graphics capabilities, computer workstation engineers have tried to design high performance, multiple window systems which maintain a high degree of user interactivity with the graphics workstation.
A primary function of window systems in such graphics systems is to provide the user with simultaneous access to multiple processes on the workstation. Each of these processes provides an interface to the user through its own area onto the workstation display. The overall result for the user is an increase in productivity since the user can then manage more than one task at a time with multiple windows displaying multiple processes on the workstation.
In graphics systems, some scheme must be implemented to "render" or draw graphics primitives to the system's screen. "Graphics primitives" are a basic component of a graphics picture, such as a polygon or vector. All graphics pictures are formed with combinations of these graphics primitives. Many schemes may be utilized to perform graphics primitives rendering. One such scheme is the "spline tessellation" scheme utilized in the TURBO SRX graphics system provided by the Hewlett Packard Graphics Technology division, Fort Collins, Colo.
The graphics rendering procedure generally takes place within a piece of graphics rendering hardware called a "frame buffer." A frame buffer generally comprises a plurality of video random access memory (VRAM) computer chips which store information concerning pixel activation on the system's display screen corresponding to the particular graphics primitives which will be traced out on the screen. Generally, the frame buffer contains all of the pixel activation data, and stores this information until the graphics system is prepared to trace this information on the workstation's screen. The frame buffer is generally dynamic and is periodically refreshed until the information stored on it is written to the screen.
Thus, computer graphics systems convert image representations stored in the computer's memory to image representations which are easily understood by humans. The image representations are typically displayed on a cathode ray tube (CRT) device that is divided into arrays of pixel elements which can be stimulated to emit a range of colored light. The particular color of light that a pixel emits is called its "value." Display devices such as CRTs typically stimulate pixels sequentially in some regular order, such as left to right and top to bottom, and repeat the sequence 50 to 70 times a second to keep the screen refreshed. Thus, some mechanism is required to retain a pixel's value between the times that this value is used to stimulate the display. The frame buffer is typically used to provide this "refresh" function.
Frame buffers, or "display processors," for displaying data in windows on display screens in graphics rendering systems are known in the art. See U.S. Pat. No. 4,780,709, Randall. As taught in the Randall patent, a display processor divides a display screen such as a CRT into a plurality of horizontal strips, with each strip being further subdivided into a plurality of "tiles." Each tile represents a portion of a window to be displayed on the screen, and each tile is further defined by tile descriptors which include memory address locations of data to be displayed in that particular tile. See Randall, col. 2, lines 23-35. The tiles generally contain a plurality of pixels, although a tile can be as small as one pixel in width. Each viewing window may be arbitrarily shaped by combinations of different tiles which are rectangularly shaped See Randall, col. 1, lines 55-67.
Since frame buffers are usually implemented as arrays of VRAMs, they are "bit mapped" such that pixel locations on a display device are assigned x,y coordinates on the frame buffer. A single VRAM device rarely has enough storage location to completely store all the x,y coordinates corresponding to pixel locations for the entire image on a display device, and therefore multiple VRAMs are generally used. The particular mapping algorithm used is a function of various factors, such as what particular VRAMs are available, how quickly the VRAM can be accessed compared to how quickly pixels can be rendered, how much hardware it takes to support a particular mapping, and other factors.
In high performance computer workstation systems, it is generally desirable to access as many pixels simultaneously as is practical. However, to access as many pixels simultaneously as possible implies that each VRAM cycle accesses all VRAMs. Furthermore, high-density VRAMs are generally much slower than the hardware that renders pixels. There is therefore a long-felt need in the art for computer graphics renderers and frame buffers which allow simultaneous access to as many pixels as are needed to render an image, thereby reducing the number of accesses required to the frame buffer to completely render the image and decreasing the time it takes to ultimately write a graphics primitive to the system's screen.
Typical CRT devices for use with graphics workstations are "raster scan" display devices. Typical raster scan display devices generate images comprising a multiplicity of parallel, non-overlapping bands of pixels comprising sets of parallel lines. An example of such a system is disclosed in U.S. Pat. No. 4,695,772, Lau et al. The raster scan device disclosed in the Lau et al. patent is organized as an array of tiles. See Lau et al, col. 2, line 36.
Raster scan devices generally utilize a multiplicity of beams for the red, green and blue (RGB) channels in the CRT. The multiplicity of beams generally write from the left side of the display CRT to the right side of the display CRT. For the purposes of dividing the CRT into tiles (a process called "tiling"), each tile is considered to comprise a height or resolution equal to the multiplicity of scan lines, with each tile being a particular number of pixels wide. The resulting graphics primitive image thus comprises a multiplicity of parallel, non-overlapping sets of parallel lines of pixels generated by a separate sweep of electron beams across the CRT screen. The tiles are generally rectangular, and thus organize the image into arrays having a plurality of rows by a set number of columnar tiles. See Lau et al., col. 4, lines 12-27.
Typically, rendering algorithms calculate consecutive pixel values for consecutive pixels with small changes in their x,y addresses from pixel to pixel. This means that there is a large degree of "coherency" in the pixel addresses. When arranging VRAMs for simultaneous pixel access, it is desirable that the pixels that are accessed are allowed to be highly coherent.
The VRAMs are arranged so that a rectangular region of the display that contains "tile-sized" pixels has one pixel accessed from each VRAM that comprises a bank. A "bank" is a slice of the depth required for each pixel, where the "depth" may be conveniently thought of as a VRAM width. The number of banks available to a pixel is thus equal to the depth of the tile divided by the VRAM width, and the "tile size" is defined as the number of VRAMs divided by the number of banks.
To illustrate this organization, consider a tile size of 16 with the VRAMs organized as a 4.times.4 array. Each VRAM may be denoted by a letter and thus, the letters A through P denote 16 particular VRAMs. In general, frame buffers are replicated in the horizontal and vertical directions and each VRAM contains multiple pixels with each instance of a VRAM denoting a unique pixel location. For a tile size of 16, 16 coherent pixels share a common VRAM address. Thus, a traditional method for physically addressing the VRAMs has evolved since, if all the VRAMs in the frame buffer are always given the same VRAM address, a rectangular group of pixels will be accessed with each VRAM cycle. This rectangular group of pixels is denoted a "tile" as previously discussed.
Prior rendering algorithms to generate pixel values sequentially generate all the pixels that make up a primitive, such as a polygon. Each primitive that comprises an image representation is used sequentially to generate pixel values. Therefore, a group of pixel values is generated which is stored in the frame buffer VRAMs. The x,y addresses of at least one of the pixels of a primitive is used to determine what row and column address should be applied to the VRAMs. Then, all the pixels in the appropriate VRAMs. However, not all pixels in the group are accessible with a first tile access, and therefore additional tiles must be accessed from the frame buffer in order for the system to write a primitive to a CRT.
The average number of pixels actually stored with each tile access is called the "tile hit rate." Since primitives are usually not rectangular, the tile hit rate can be rather low because each access to the frame buffer cannot hit every row and column address for each pixel outside of a rectangular region. There is therefore a long-felt need in the art to improve tile hit rates on frame buffer computer graphics systems. This long-felt need in the art has not heretofore been adequately met by any prior rendering algorithms or computer workstation frame buffers and renderers.